package com.songyang.yougnsql.core.index;

import com.songyang.yougnsql.common.ErrorMsg;
import com.songyang.yougnsql.common.LogHelper;
import com.songyang.yougnsql.common.YoungSQLException;
import com.songyang.yougnsql.core.data.DataManager;
import com.songyang.yougnsql.core.data.dataItem.DataItem;
import com.songyang.yougnsql.core.transaction.TransactionManager;
import com.songyang.yougnsql.core.utils.ByteUtils;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @ClassName BPlusTree
 * @Description
 * @date 2022/12/22 13:39
 * @Author yanceysong
 * @Version 1.0
 */
public class BPlusTree {
    private final Logger logger = LogManager.getLogger(BPlusTree.class);
    public DataManager dataManager;
    /**
     * 当前根节点的uid（load时候通过uid解析到bootDataItem）
     */
    public long bootUid;
    /**
     * 存放着根节点的数据
     */
    public DataItem bootDataItem;
    public Lock bootLock;

    /**
     * 刚开始创建b+树的时候，就创建了一个空的根节点，然后把根节点的位置返回
     *
     * @param dataManager dm
     * @return 根节点的uid
     */
    public static long create(DataManager dataManager) throws Exception {
        byte[] nilRootRaw = Node.newNilRootRaw();
        long rootUid = dataManager.insert(TransactionManager.SUPER_XID, nilRootRaw);
        //把头结点的位置插入到页面里，然后把位置返回
        return dataManager.insert(TransactionManager.SUPER_XID, ByteUtils.long2Byte(rootUid));
    }

    /**
     * 通过一个根节点加载一颗二叉树
     *
     * @param rootUid     根节点的uid
     * @param dataManager dm
     * @return 加载好的二叉树
     * @throws Exception 异常
     */
    public static BPlusTree loadBPlusTree(long rootUid, DataManager dataManager) throws Exception {
        DataItem bootDataItem = dataManager.read(rootUid);

        if (bootDataItem == null) throw new YoungSQLException(ErrorMsg.PARAM_ILLEGAL_EXCEPTION);
        BPlusTree bPlusTree = new BPlusTree();
        bPlusTree.dataManager = dataManager;
        bPlusTree.bootDataItem = bootDataItem;
        bPlusTree.bootUid = rootUid;
        bPlusTree.bootLock = new ReentrantLock();
        return bPlusTree;
    }

    /**
     * 在b+树当中根据节点的uid和要查询的key返回下一层的节点
     *
     * @param nodeUid 节点的uid
     * @param key     key
     * @return 查询下一层的node节点
     * @throws Exception 异常
     */
    private long searchNext(long nodeUid, long key) throws Exception {
        while (true) {
            Node node = Node.loadNode(this, nodeUid);
            Node.SearchNextRes searchResult = node.searchNext(key);
            node.release();
            //如果返回了uid就直接返回，如果没有则去他的兄弟节点继续查找
            if (searchResult.uid != Node.NODE_DATA_IS_NULL) return searchResult.uid;
            nodeUid = searchResult.siblingUid;
        }
    }

    /**
     * 在叶子节点中找打key的数据地址
     *
     * @param nodeUid 节点的uid
     * @param key     key
     * @return key对应的uid
     * @throws Exception 异常
     */
    private long searchLeaf(long nodeUid, long key) throws Exception {
        //加载这个node
        Node node = Node.loadNode(this, nodeUid);
        boolean isLeaf = node.isLeaf();
        node.release();
        //如果当前节点是叶子节点，那么他的uid就是key的uid，否则是他孩子的uid，递归查询直到查到叶子节点
        return isLeaf ? nodeUid : searchLeaf(searchNext(nodeUid, key), key);
    }

    /**
     * 根据key在b+树中找到他的uid
     *
     * @param key key
     * @return uid
     */
    public List<Long> search(long key) throws Exception {
        return searchRange(key, key);
    }

    /**
     * 根据查询某一个范围内的数据
     *
     * @param leftKey  最小的key
     * @param rightKey 最大的key
     * @return 查到的范围数据
     */
    public List<Long> searchRange(long leftKey, long rightKey) throws Exception {
        long rootUid = rootUid();
        LogHelper.info(logger, "select 根节点的uid:{}", rootUid);
        //找到左节点的uid
        long leafUid = searchLeaf(rootUid, leftKey);
        ArrayList<Long> uids = new ArrayList<>();
        while (true) {
            Node leafNode = Node.loadNode(this, leafUid);
            //在当前节点找到满足条件的数据
            Node.LeafSearchRangesRes result = leafNode.leafSearchRange(leftKey, rightKey);
            leafNode.release();
            uids.addAll(result.uids);
            //如果他的兄弟节点不为零，就说明可能还有数据在其兄弟节点，继续其兄弟节点
            if (result.siblingUid == Node.NODE_DATA_IS_NULL) {
                break;
            } else {
                leafUid = result.siblingUid;
            }
        }
        return uids;
    }

    /**
     * 对外使用，在b+树插入一组数据
     *
     * @param key key
     * @param uid 资源的uid
     * @throws Exception 异常
     */
    public void insert(long key, long uid) throws Exception {
        long rootUid = rootUid();
        LogHelper.info(logger, "insert->BPlus:根节点的uid:{}", rootUid);
        InsertRes insertResult = insert(rootUid, uid, key);
        if (insertResult.newNode != Node.NODE_DATA_IS_NULL) {
            updateRootUid(rootUid, insertResult.newNode, insertResult.newKey);
        }
    }

    /**
     * 在node节点上插入一组数据
     *
     * @param nodeUid node节点的uid
     * @param uid     资源的uid
     * @param key     key
     * @return 插入的结果
     * @throws Exception 异常
     */
    private InsertRes insert(long nodeUid, long uid, long key) throws Exception {
        Node node = Node.loadNode(this, nodeUid);
        boolean isLeaf = node.isLeaf();
        node.release();
        //如果是叶子节点
        if (isLeaf) {
            //直接插进去然后看是否需要分割
            return insertAndSplit(nodeUid, uid, key);
        } else {
            //就找到这个key的子节点
            long nextNodeUid = searchNext(nodeUid, key);
            InsertRes insertRes = insert(nextNodeUid, uid, key);
            if (insertRes.newNode != Node.NODE_DATA_IS_NULL) {
                return insertAndSplit(nodeUid, insertRes.newNode, insertRes.newKey);
            } else return new InsertRes(Node.NODE_DATA_IS_NULL, Node.NODE_DATA_IS_NULL);
        }
    }

    /**
     * 在node节点上插入，如果需要分割的话，就进行分割
     *
     * @param nodeUid node节点的uid
     * @param uid     uid
     * @param key     key
     * @return 插入结果
     * @throws Exception 异常
     */
    private InsertRes insertAndSplit(long nodeUid, long uid, long key) throws Exception {
        while (true) {
            Node node = Node.loadNode(this, nodeUid);
            Node.InsertAndSpiltRes insertResult = node.insertAndSpilt(uid, key);
            node.release();
            if (insertResult.siblingUid != Node.NODE_DATA_IS_NULL) {
                nodeUid = insertResult.siblingUid;
            } else {
                return new InsertRes(insertResult.newSon, insertResult.newKey);
            }
        }
    }

    /**
     * 关闭资源
     */
    public void close() {
        bootDataItem.release();
    }

    /**
     * 返回根节点的uid
     *
     * @return 根节点的uid
     */
    private long rootUid() {
        bootLock.lock();
        try {
            byte[] data = bootDataItem.data();
            return ByteUtils.parseLong(Arrays.copyOfRange(data, 0, 8));
        } finally {
            bootLock.unlock();
        }
    }

    /**
     * 更新根节点的uid
     *
     * @param left     左节点的uid
     * @param right    右节点的uid
     * @param rightKey 右节点的key
     * @throws Exception 异常
     */
    private void updateRootUid(long left, long right, long rightKey) throws Exception {
        bootLock.lock();
        try {
            byte[] rootRaw = Node.newRootRaw(left, right, rightKey);
            long newRootUid = dataManager.insert(TransactionManager.SUPER_XID, rootRaw);
            bootDataItem.before();
            byte[] data = bootDataItem.data();
            System.arraycopy(ByteUtils.long2Byte(newRootUid), 0, data, 0, 8);
            bootDataItem.after(TransactionManager.SUPER_XID);
        } finally {
            bootLock.unlock();
        }
    }

    protected static class InsertRes {
        long newNode, newKey;

        public InsertRes(long newNode, long newKey) {
            this.newNode = newNode;
            this.newKey = newKey;
        }
    }
}
